package ljl.alg.wangzheng_camp.round1.dp;

import java.util.Arrays;

public class _69_min_path {
    
    /**
     * 这个有两种写法，一个是声明 dp 长度 n，此时初始化第一个元素为 0 即可
     * 另一个是声明 dp 长度为 n + 1，此时要声明第二个元素为 0，不然结果就错了
     *
     * 前一种，需要判断 j == 0 的情况，后者不好想，但是省去了特殊情况
     * */
    public int minPathSum(int[][] grid) {
        int n = grid[0].length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[1] = 0;
        for (int[] line : grid) {
            for (int j = 1; j <= n; j++) {
                dp[j] = Math.min(dp[j - 1], dp[j]) + line[j - 1];
            }
        }
        return dp[n];
    }
}
